package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-26 16:09
 */


import java.time.chrono.IsoChronology;
import java.util.*;
import java.util.logging.XMLFormatter;

/**
 * 全排列 II
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class lc47 {
    boolean[] isUse;

    public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();

        isUse = new boolean[nums.length];
        Arrays.sort(nums);//排序，让相同的数字临近

        dfs(nums, ans, list, 0);
        return ans;
    }

    public void dfs(int[] nums, List<List<Integer>> ans, List<Integer> list, int idx) {

        //个数够了，返回
        if (idx == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {

            //剔除重复结果（优先使用左侧的）
            if (isUse[i] || (i > 0 && nums[i] == nums[i - 1] && !isUse[i - 1])) {//i-1未被
                continue;
            }
            //加入list
            list.add(nums[i]);
            isUse[i] = true;

            dfs(nums, ans, list, idx + 1);

            isUse[i] = false;
            //回溯时，自idx回溯
            list.remove(idx);
        }

    }

}
